//给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。 
//
// 二叉搜索树的定义如下： 
//
// 
// 任意节点的左子树中的键值都 小于 此节点的键值。 
// 任意节点的右子树中的键值都 大于 此节点的键值。 
// 任意节点的左子树和右子树都是二叉搜索树。 
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
//输出：20
//解释：键值为 3 的子树是和最大的二叉搜索树。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：root = [4,3,null,1,2]
//输出：2
//解释：键值为 2 的单节点子树是和最大的二叉搜索树。
// 
//
// 示例 3： 
//
// 
//输入：root = [-4,-2,-5]
//输出：0
//解释：所有节点键值都为负数，和最大的二叉搜索树为空。
// 
//
// 示例 4： 
//
// 
//输入：root = [2,1,3]
//输出：6
// 
//
// 示例 5： 
//
// 
//输入：root = [5,4,8,3,null,6,3]
//输出：7
// 
//
// 
//
// 提示： 
//
// 
// 每棵树有 1 到 40000 个节点。 
// 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。 
// 
// 👍 83 👎 0


package leetcode.editor.cn;

//二叉搜索子树的最大键值和

import Entity.TreeNode;
import 分类.二叉搜索树;
import leetcode.editor.cn.level.困难;

public class P1373_二叉搜索子树的最大键值和 implements 困难, 二叉搜索树 {
    public static void main(String[] args) {
        Solution solution = new P1373_二叉搜索子树的最大键值和().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 思路：
         * 采用后序遍历进行处理
         * 计算下列值
         * 使用一个数组进行保存 int[]
         * 0-当前节点下的是否是BST
         * 1-当前节点为根的 最小值
         * 2-当前节点为根的 最大值
         * 3-总和
         *
         * @param root
         * @return
         */
        int sum = 0;
        public int maxSumBST(TreeNode root) {
            traverse(root);
            return sum;
        }

        private int[] traverse(TreeNode root) {
            if (root == null) {
                return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
            }
            int[] left = traverse(root.left);
            int[] right = traverse(root.right);
            // 处理当前节点
            int[] res = new int[4];
            // 如果当前节点的左右子树都是BST 并且根节点大于左子树的最大值 小于右子树的最小值
            if (left[0] == 1 && right[0] == 1
                    && root.val > left[2] && root.val < right[1]) {
                // 计算根节点的左子树最大值 右子树最小值
                res[0] = 1;
                res[1] = Math.min(left[1], root.val);
                res[2] = Math.max(right[2], root.val);
                res[3] = left[3] + right[3] + root.val;
                sum = Math.max(sum, res[3]);
            } else {
                res[0] = 0;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}